package palindrome;


public class ShorestPalindrome {

	public static void main(String[] args) {
		ShorestPalindrome object = new ShorestPalindrome();
		object.shortestPalindrome2("aacecaaa");
	}

	//Given a string S, you are allowed to convert it to a palindrome by adding characters in front of it. 
//	Find and return the shortest palindrome you can find by performing this transformation.
	
	//这道题只能在前面添加，所以我们只需找出开头到结束的最大回文子串长度即可
	public String shortestPalindrome(String s) {
		if(s == null || s.length() <= 0){
			return s;
		}
		int length = s.length();
		int i;
		for(i = length; i >= 1; i--){
			//这样判断太耗时了
			if(isPalidrome(s.substring(0, i))){
				break;
			}
		}
		StringBuilder builder = new StringBuilder();
		for (int j = 0; j < length - i; j++) {
			builder.append(s.charAt(length - 1 - j));
		}
		builder.append(s);
		return builder.toString();
	}
	
	//判断是否是回文
	public boolean isPalidrome(String string){
		string.equals("");
		int length = string.length();
		for (int i = 0; i < length  / 2; i++) {
			if(string.charAt(i) != string.charAt(length - 1 - i)){
				return false;
			}
		}
		return true;
	}
	
	
	
	//无非就是找到以0开始的最长的回文子串，假设s的0...j是回文
	//那么对于inverse 的s,一定有s[0...j]  == reverse[length - 1 - j ... length - 1]
	//用图形来表示：
	//           |---------|~~~~~~
	//     ~~~~~~|---------|
	//看到这个有没有很熟悉！！！对前后缀长度
	//可是两个字符串怎么找前后缀呢? 拼接
	public String shortestPalindrome2(String s) {
		if(s == null || s.length() <= 0){
			return s;
		}
		StringBuilder sb = new StringBuilder(s);
		//加一个"#"是为了防止判断超过长度
		String temp = s + "#" + sb.reverse();
		
//		int[] table = new int[temp.length()];
//		getNextArray(temp.toCharArray(), table);
//		
		int[] table = next(temp);
		
		for (int i = 0; i < table.length; i++) {
			System.out.print(table[i] + " ");
		}
		System.out.println();
		int length = s.length();
		int palidromeLength = table[table.length - 1];
		System.out.println(" " + palidromeLength);
		StringBuilder builder = new StringBuilder();
		for (int j = 0; j < length - palidromeLength; j++) {
			builder.append(s.charAt(length - 1 - j));
		}
		builder.append(s);
		return builder.toString();
	}
	
	public static void getNextArray(char[] target, int[] next){
		 int q, k = 0;//q:模版字符串target下标；k:最大前后缀长度
		 int length = target.length;
		 next[0] = 0;//模版字符串的第一个字符的最大前后缀长度为0
		 for(q = 1; q < length; q++){
//			 if(target[q] == target[next[q - 1]]){
//		            next[q] = next[q - 1] + 1;
//		     }
			 //退出的条件要么是k等于0，此时后面的if判断中如果相等，那么最大公共长度就是1 
			 //要么就是找到了与target[q]相等的
			 //int count = 0;
			 
			 
			 //既然是移动，那么就不必在里面写while了，原文用的是while，只需写if即可
			 //我错了，还是要使用while，在测试用例中是可以找到的，但是如果不使用while，用if那么就会出现问题
			 //之所以这样是因为kmp的移动并不是一次到位的
			 //abbababb....    查找abbabb时，会出现第6个不匹配，此时kmp算法只移动了3 （5 - 2），所以需要while
			 while(k > 0 && target[q] != target[k]){
				 //这个while循环是整个next函数的关键
				 //如果不相等，就说明P[0]···P[k-1] 与 p[q - 1] ...p[q - k]是匹配成功的，看到这里有没有很熟悉
				 //对的，又是重复利用了Kmp的思想，如果模式串中的不匹配，那么只移动模式串中的值！！！
				 //要移动     =  已经匹配的长度(也就是  k)  - next[k - 1]
				 //所以最后剩下的匹配长度   =  k - 移动的数目
				 //System.out.println("count " + count);
				 k = next[k - 1]; 
			 }
			 //count = 0;
			 //如果相等，那么最大相同前后缀长度加1
			 if(target[q] == target[k]){ 
//				 System.out.println(" kk"+ q + " " + k);
				 k++;
			 }
			 next[q] = k;
//			 System.out.println("nxt " + q +"  "+ next[q]);
		 }
//		 System.out.println(" kk" + k);
//		 for (int i : next) {
//			System.out.print(" " + i);
//		 }
//		 System.out.println("------");
	}
	
	public int[] next(String pattern){
		if(pattern == null || pattern.length() <= 0){
			return new int[]{};
		}
		int length = pattern.length();
		
		char[] chas = pattern.toCharArray();
		int[] next = new int[length];
		next[0] = 0;
		
		int k = 0, index = 1;
		for (; index < length; index++) {
			if(chas[index] == chas[k]){
				//匹配的话
				k++;
				//next[index] = next[index - 1] + 1;
			}else{
				//不匹配的话 ，我们移动k就行
				//这儿也是一个kmp的思想
				while(k > 0 && chas[index] != chas[k]){
					k = next[k - 1];
				}
				if(chas[index] == chas[k]){
					k++;
				}
			}
			next[index] = k;
		}
		return next;
	}
}
